#include "sort.h"

void adjust_down(vector<int>& vc, int sz, int parent){
  int child = parent*2+1;
  while(child < sz)
  {
    if(child+1 < sz && vc[child+1] > vc[child])
    {
      ++child;
    }
    if(vc[child] > vc[parent])
    {
      swap(vc[child], vc[parent]);
      parent = child;
      child = parent*2+1;
    }
    else{
      break;
    }
  }
}

void HeapSort(vector<int>& vc){
  for(int i = (vc.size()-2)/2; i>=0; --i)
  {
    adjust_down(vc, vc.size(), i);
  }

  for(int end = vc.size()-1; end>0; --end)
  {
    swap(vc[0], vc[end]);
    adjust_down(vc, end, 0);
  }
}
